package 简单;

/*
* 根据数字二进制下 1 的数目排序
* 力扣地址：https://leetcode-cn.com/problems/sort-integers-by-the-number-of-1-bits/
*
* 给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
* 如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
* 请你返回排序后的数组。
* 示例 1：
* 输入：arr = [0,1,2,3,4,5,6,7,8]
* 输出：[0,1,2,4,8,3,5,6,7]
* 解释：[0] 是唯一一个有 0 个 1 的数。
* [1,2,4,8] 都有 1 个 1 。
* [3,5,6] 有 2 个 1 。
* [7] 有 3 个 1 。
* 按照 1 的个数排序得到的结果数组为 [0,1,2,4,8,3,5,6,7]
* 思路：先计算出每个数1的个数，然后利用Comparable排序
*
* */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;

public class demo1356 {

    public static void main(String[] args) {

        int[] a = {0,1,2,3,4,5,6,7,8};
//        int[] a = {1024,512,256,128,64,32,16,8,4,2,1};

        System.out.println(Arrays.toString(sortByBits(a)));

    }


    public static int[] sortByBits(int[] arr) {

        ArrayList<Bits> list = new ArrayList<>();

        for (int i=0;i<arr.length;i++){
            list.add(new Bits(arr[i]));
        }

        Collections.sort(list);

        int[] bs = new int[list.size()];
        int count = 0;
        Iterator<Bits> iterator = list.iterator();

        while (iterator.hasNext())
        {
            bs[count++] = iterator.next().number;
        }

        return bs;
    }

    static class Bits implements Comparable<Bits>{

        int number;
        int OneCount;

        public Bits(int n){
            this.number = n;
            this.OneCount = this.setOneCount(n);
        }

        private int setOneCount(int n){
            String tn = Integer.toBinaryString(n);
            int cn = 0;

            for (int i=0;i<tn.length();i++){

                if(tn.charAt(i) == '1')
                    cn++;

            }
//            System.out.println(cn);

            return cn;
        }


        @Override
        public int compareTo(Bits o) {

            if (this.OneCount == o.OneCount)
            {
                if (this.number > o.number)
                    return 1;
                else
                    return -1;
            }
            else
            {
                if (this.OneCount < o.OneCount)
                    return -1;
                else
                    return 1;

            }
        }
    }


}
